import java.util.*;

public class Solution909 {
    class BpEle{
        int num;
        int step;
        public BpEle(int num, int step) {
            this.num = num;
            this.step = step;
        }
    }

    public int snakesAndLadders(int[][] board) {
        Map<Integer,Integer> index=new HashMap<>();
        int tmpNum=1;
        int rowMod=0;
        for (int i = board.length-1; i >= 0; i--) {
            int[] tmpRow=board[i];
            if((rowMod&1)==0){
                for (int j = 0; j < tmpRow.length; j++) {
                    index.put(tmpNum++,tmpRow[j]);
                }
            }
            else{
                for (int j = tmpRow.length-1; j >= 0; j--) {
                    index.put(tmpNum++,tmpRow[j]);
                }
            }
            rowMod++;
        }
        int target=tmpNum-1;
        Queue<BpEle> bpQueue=new LinkedList<>();
        BitMap seen=new BitMap(1000);
        bpQueue.offer(new BpEle(1,0));
        while(!bpQueue.isEmpty()){
            BpEle tmpLoc=bpQueue.poll();
            if(tmpLoc.num==target){
                return tmpLoc.step;
            }
            for (int i = 1; i <= 6; i++) {
                int newLoc=tmpLoc.num+i;
                int moveTo=index.getOrDefault(newLoc,-1);
                newLoc=moveTo==-1? newLoc:moveTo;
                if(newLoc>target){
                    continue;
                }
                if(!seen.contains(newLoc)){
                    bpQueue.offer(new BpEle(newLoc,tmpLoc.step+1));
                    seen.put(newLoc);
                }
            }
        }
        return -1;
    }
}
